/////////////////////////////////////////////////////////////////////////////
// Data structures  
/////////////////////////////////////////////////////////////////////////////

#ifndef _VISUALISER_TOOLKIT__H_
#define _VISUALISER_TOOLKIT__H_

////////////////////////////////////////////////////////////////////////////////
// Includes
////////////////////////////////////////////////////////////////////////////////

#include <vector>
#include <iostream>

////////////////////////////////////////////////////////////////////////////////
// Namespaces
////////////////////////////////////////////////////////////////////////////////

namespace SC {

////////////////////////////////////////////////////////////////////////////////
// Implementation
////////////////////////////////////////////////////////////////////////////////

class VisualiserToolkit {

	public:

	/// Finds the size of the inside circles given the amount of circles
	static const double FindInsideCirclesSize(const unsigned int nb_circles) {
		if (nb_circles == 0) return 0.;
		static const unsigned int nb_terms = 5;
		static const unsigned int terms[nb_terms] = { 2, 3, 4, 5, 7 };
		static const double sizes[nb_terms] = { 1./2., 1./(1.+sqrt(4./3.)), 1./(1.+sqrt(2.)), 1./(1.+sqrt(2 + sqrt(4./3.))), 1./3. };
		std::vector<unsigned int> dec = find_best_decomposition(nb_circles, terms, nb_terms);
		double s = 1.;
		for (unsigned int i=0; i<dec.size(); ++i)
			s *= sizes[dec[i]];
		return s;
	}

	protected:

	/// Finds best decomposition of the given number given a list of terms
	static const std::vector<unsigned int> find_best_decomposition(
		const unsigned int nb,
		const unsigned int * terms,
		const unsigned int nb_terms
	) {
		if (nb <= terms[nb_terms-1]) {
			for (unsigned int i=0; i<nb_terms; ++i)
				if (terms[i] >= nb)
					return std::vector<unsigned int>(1,i);
			/// Should never happen
			std::cerr << "ERROR find_best_decomposition" << std::endl;
			return std::vector<unsigned int>();
		}
		else {
			std::vector<unsigned int> best;
			for (int i=nb_terms-1; i>=0; --i) {
				// Get solutions
				std::vector<unsigned int> prod = find_best_decomposition((unsigned int)ceil(((double)nb)/((double)terms[i])), terms, nb_terms);
				prod.push_back(i);
				// Early exit condition
				if (!best.empty() && prod.size() > best.size()) break;
				// Compare with best solution
				if (best.empty() || (eval_decomposition(prod, terms) < eval_decomposition(best, terms)))
					best = prod;
			}
			return best;
		}
	}

	/// Evaluates decomposition
	static const unsigned int eval_decomposition(
		const std::vector<unsigned int> & dec,
		const unsigned int * terms
	) {
		unsigned int res = 1;
		for (unsigned int i=0; i<dec.size(); ++i)
			res *= terms[dec[i]];
		return res;
	}

};

////////////////////////////////////////////////////////////////////////////////
// Closing Namespaces
////////////////////////////////////////////////////////////////////////////////

}

////////////////////////////////////////////////////////////////////////////////

#endif
